/**
 *
 */
package 算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.IntStream;

import org.junit.Test;

import com.google.common.primitives.Ints;

/**
 * @Title:
 * @author zhoujie
 * @date 2018年7月18日 下午7:45:53
 *
 */
public class 空间换时间 {
    private static void spaceToTime(Integer[] arr) {
		/*int max =arr[0];
		for(int i=1;i<arr.length;i++) {
        	if(arr[i]>max) {
        		max=arr[i];
        	}
        }*/
        int max = Arrays.stream(arr).max(Integer::compareTo).get();
        int[] temp = new int[max + 1];
        for (int i : arr) {
            temp[arr[i]] = arr[i];
        }
        int j = 0;
        for (int i = 0; i < max; i++) {
            if (temp[i] > 0) {
                arr[j++] = temp[i];
            }
        }
    }

    @Test
    public void test01() {
        int[] arr = IntStream.range(0, 10000000).toArray();
        List<Integer> arrayList = new ArrayList(Arrays.asList(arr));
        Collections.shuffle(arrayList);//打乱顺序
        // List<Integer> arrayList2=new ArrayList<>(arrayList);//拷贝一份
        Integer[] a1 = new Integer[arrayList.size()];
        Integer[] a2 = new Integer[arrayList.size()];

        arrayList.toArray(a1);
        arrayList.toArray(a2);
        long startTime = System.currentTimeMillis();
        Arrays.sort(a1);
        System.out.println("自带排序时间：" + (System.currentTimeMillis() - startTime));
        startTime = System.currentTimeMillis();
        spaceToTime(a2);
        System.out.println("新排序时间：" + (System.currentTimeMillis() - startTime));
    }

    public static void main(String[] args) {
        int[] arr = IntStream.range(0, 20000000).toArray();
        List<Integer> arrayList = Ints.asList(arr);
        Collections.shuffle(arrayList);//打乱顺序
        Integer[] a1 = arrayList.stream().toArray(Integer[]::new);
        Integer[] a2 = arrayList.stream().toArray(Integer[]::new);
        long startTime = System.currentTimeMillis();
        Arrays.sort(a1);
        System.out.println("自带排序时间：" + (System.currentTimeMillis() - startTime));
        startTime = System.currentTimeMillis();
        Arrays.parallelSort(a2);
        System.out.println("新排序时间：" + (System.currentTimeMillis() - startTime));
    }
}                                                                          
